package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:50:44 
* @Description：
* 
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
今天测试组开完会后,他又发话了:
在古老的一维模式识别中,
常常需要计算连续子向量的最大和,
当向量全为正数的时候,问题很好解决。
但是,如果向量中包含负数,是否应该包含某个负数,
并期望旁边的正数会弥补它呢？
例如:{6,-3,-2,7,-15,1,2,2},
连续子向量的最大和为8(从第0个开始,到第3个为止)。
给一个数组，返回它的最大连续子序列的和，
你会不会被他忽悠住？
(子向量的长度至少是1)
*/
public class A30连续子数组的最大和 {
	
	//错误示例
	 public static int FindGreatestSumOfSubArray(int[] array) {
			int result=array[0];
	        for(int i=0;i<array.length;i++) {
	        	int temp=array[i];
	        	for (int j = i+1; j < array.length; j++) {
					temp+=array[j];       
				}
	        	if (temp>=result) {                              //暴力破解,思路不对
					result=temp;                                //两层循环，每次循环找出N,N-1,N-2……2，1长度的最大值
				} 													//内层循环结束后，比较值，只保留最大值
	        }                                                 //问题在于，每次循环出来的结果都是从头到尾到算进去了（伪子数组）
			return result; 							//其实最大的连续数组不到一定会到头，可以是在中间的，这里有问题
	    }
	
   //上面方法的正确修改
	 //一定要清楚，组成最大和的连续数组不一定是要在头或者是尾上，可以是中间的。
	public static int FindGreatestSumOfSubArray11(int[] array) {
		if (array == null) {
			return Integer.MIN_VALUE;
		}
		int maxCur = 0; // 保存返回的结果
		int totalNum = 0; // 保存从某个位置为起点累加所有的数，得到的和
		for (int i = 0; i < array.length; i++) {
			// 最大连续子序列的和不一定从第一个元素开始算起
			// 当前面的数之和小于当前元素，并且前面数的和为负数时，将当前元素作为新的起点
			//*** 这个条件改了很多次
			
			// 这里的totalNum一定要是小于0的，小于0就可以判定前面的子序列之和为0，要找最大值，肯定是要正整数的>0
			//所以在这里，就可以确定前面的子序列一定不是连续子数组的最大和的组成部分，可以重新确定下标开始计算后面的子序列的和
			if (totalNum < array[i] && totalNum < 0) { 
				maxCur = array[i];
				totalNum = array[i];                  //这步就是重新确定下标和初始值
			} else {
				totalNum += array[i];
				if (totalNum > maxCur) {
					maxCur = totalNum;
				}
			}
		}
		return maxCur;
	}
	 
	 
	 //动态规划才是正道
	 public static int FindGreatestSumOfSubArray22(int[] array) {
		 int len = array.length;
		 int [] dp=new int[len];       
		 int max=array[0];                          //把arr[0]作为sum的基础值进行比较，也是为了后面循环中i=1时，不漏掉arr[0]
		 dp[0]=array[0];                        //dp[0]得是arr[0]
		 for(int i=1;i<len;i++) {
			 int tempSum=dp[i-1]+array[i];   //这里巧妙，当i=1，dp[i-1]+arr[i]=>arr[0]+arr[1]
			 if (tempSum>array[i]) {              //再往后循环，就是相邻两个数的求和过程了
				dp[i]=tempSum;                //dp[i]用来保存临时结果
			}else {
				dp[i]=array[i];
			}
			 if (dp[i]>max) {
				max=dp[i];
			}
		 }
		 return max;
	 }
	 
	 public static void main(String[] args) {
		 Scanner scanner = new Scanner(System.in);
			String s = scanner.nextLine();
			String[] ss = s.split(" ");
			int [] arr=new int [ss.length];
			for (int i = 0; i < arr.length; i++) {
				arr[i]=Integer.parseInt(ss[i]);
			}
			int sum = FindGreatestSumOfSubArray(arr);
			System.out.println(sum);
			int sum11 = FindGreatestSumOfSubArray11(arr);
			System.out.println(sum11);
			int sum22 = FindGreatestSumOfSubArray22(arr);
			System.out.println(sum22);
	}

}
